package practice;

public class questions {
    class TreeNode{
        public int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 判断两棵树是否相同
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q){
        if(p == null && q == null){
            return true;
        }
        if(p != null && q == null || p == null && q != null){
            return false;
        }
        //都不为空
        if(p.val != q.val){
            return false;
        }
        //对子树进行判断
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    /**
     * 判断是不是子树
     * 时间复杂度：O(m*n)
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }


    /**
     * 翻转二叉树
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if(root == null)  return null;

        if(root.left == null && root.right == null)   return root;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.right);
        invertTree(root.left);

        return root;
    }




    /**
     * 平衡二叉树
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {

    }



    /**
     * 对称二叉树
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root){

    }


}
